// Package day_12_dp 7-343
// @Title day_12_dp
// @Description  整数拆分
// @Author  == 琳琳也叫王木木 ==  2021/9/6 17:19
// @Create  2021/9/6 17:19
package day_12_dp

func IntegerBreak(n int) int {
	dp := make([]int, n+1)
	dp[2] = 1
	for i := 3; i <= n; i++ {
		for j := 1; j < i-1; j++ {
			dp[i] = max(dp[i], max((i-j)*j, dp[i-j]*j))
		}
	}
	return dp[n]
}
